#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
	void quicksort(vector<int>& nums) {
		if (nums.size() < 1)return;
		sort(nums,0, nums.size()-1);
	}
private:
	void sort(vector<int>& nums, int left, int right) {
		if (left >= right)return;
		int pivot = nums[right];
		int i = left;
		for (int j = left; j < right; j++) {
			if (nums[j] <= pivot) {
				swap(nums[i], nums[j]);
				i++;
			}
		}
		swap(nums[i], nums[right]);
		sort(nums, left, i - 1);
		sort(nums, i + 1, right);
	}
};
int main() {
	vector<int> aa = { 5, 2, 9, 3, 7, 6, 1, 8, 4 };
	Solution s;
	s.quicksort(aa);
	for (int a : aa) {
		cout << a << " ";
	}
	return 0;
}